

/**
 * @author VernHe
 * @date 2021年05月10日 14:42
 */
public class Solution_032 {
    public static void main(String[] args) {
        System.out.println(new Solution_032().longestValidParentheses(")()())"));
    }

    public int longestValidParentheses(String s) {
        int res = 0;
        // 参数判断
        int len = s.length();
        if (len < 2) {
            return res;
        }
        // dp数组，dp[i]表示以第i+1个字符结尾的字符串的最长有效括号数
        int[] dp = new int[len];;
        dp[0] = 0;
        char[] chars = s.toCharArray();

        for (int i = 1; i < len; i++) {
            char c = chars[i];
            if (c == ')') {
                // 能到这里说明chars[i] == ')'

                // 和前一个匹配, 例如： ****()
                if (chars[i - 1] == '(') {
                    dp[i] = i >= 2 ? dp[i - 2] + 2 : 2;
                }else if (chars[i - 1] == ')' && i - dp[i-1] - 1 >= 0 && chars[i - dp[i-1] - 1] == '(') {
                    // 如果前一个是)，那么检查是否是  ****((()))这种情况
                    dp[i] =dp[i - 1] + 2 + (i - dp[i -1] - 2 >= 0 ? dp[i - dp[i -1] - 2] : 0);
                }
            }
            res = Math.max(res,dp[i]);
        }
        return res;
    }
}
